package pers.qianyu.month_202012.date_20201221;

import org.junit.*;

/**
 * 486. 预测赢家
 * https://leetcode-cn.com/problems/predict-the-winner/
 * - 递归
 * - 动态规划
 *
 * @author mizzle rain
 * @date 2020-12-21 13:54
 */
public class PredictTheWinner {
    // 递归解法
    public boolean predictTheWinner(int[] nums) {
        int len = nums.length;
        if ((len & 1) == 0) {
            return true;
        }
        return recur(nums, 0, len - 1) >= 0;
    }

    private int recur(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int left = recur(nums, start + 1, end);
        int right = recur(nums, start, end - 1);
        return Math.max(nums[start] - left, nums[end] - right);
    }

    // 动态规划解法
    public boolean predictTheWinner2(int[] nums) {
        int len = nums.length;
        if ((len & 1) == 0) {
            return true;
        }
        // dp[i][j] 表示从数组 [i ... j] 中选最大赢面
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = nums[i];
        }
        // 当 i > j 的时候没有意义
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        //Arrays.stream(dp).forEach(i -> System.out.println(Arrays.toString(i)));
        return dp[0][len - 1] >= 0;
    }

    @Test
    public void test1() {
        int[] arr = {1, 5, 2};
        boolean result = new PredictTheWinner().predictTheWinner2(arr);
        Assert.assertFalse(result);
    }
}
